/**
 * 对每一格有进入成本，有等待成本，
 * 问从左上到右下的最小成本
 * 注意到按照题目要求左上角是没有等待成本的，直接设为0
 * 
 * 令Dij为到达ij需要的最小成本，注意该值不包含ij本身的等待成本
 * 则
 * Dij = ij的进入成本 + min(D[i-1][j]+Wait[i-1][j], D[i][j-1]+Wait[i][j-1])
 */

class Solution {

using llt = long long;
using vll = vector<llt>;

int N, M;
vector<vll> D;
enum {None = -1};

public:
    long long minCost(int m, int n, vector<vector<int>>& waitCost) {
        waitCost[0][0] = 0;
        N = m, M = n;
        if(1 == N and 1 == M) return 1;

        D.assign(N, vll(M, None));
        D[0][0] = 1;
        for(int i=0;i<N;++i)for(int j=0;j<M;++j){
            if(0 == i and 0 == j) continue;

            if(i > 0){
                auto t = D[i - 1][j];
                t += waitCost[i - 1][j];
                chkmin(D[i][j], t);
            }
            if(j > 0){
                auto t = D[i][j - 1];
                t += waitCost[i][j - 1];
                chkmin(D[i][j], t);
            }
            D[i][j] += (i + 1LL) * (j + 1LL);
        }
        return D[N - 1][M - 1];
    }
    void chkmin(llt & d, llt a){
        if(None == a) return;
        if(None == d or a < d) d = a;
    }
};
